package com.lun.swordtowardoffer2.c15;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class AlienOrder {

	public String alienOrder(String[] words) {
		
		Map<Character, Set<Character>> graph = new HashMap<>();
		Map<Character, Integer> inDegrees = new HashMap<>();
		
		
		for(String word : words) {
			for(char ch : word.toCharArray()) {
				graph.putIfAbsent(ch, new HashSet<Character>());
				inDegrees.putIfAbsent(ch, 0);
			}
		}
		
		for(int i = 1; i < words.length; i++) {
			String w1 = words[i - 1];
			String w2 = words[i];
			
			if(w1.startsWith(w2) && !w1.equals(w2)) {//针对例如"abc","ab"
				return "";
			}
			
			for(int j = 0; j < w1.length() && j < w2.length();j++) {
				char c1 = w1.charAt(j);
				char c2 = w2.charAt(j);
				if(c1 != c2) {
					if(!graph.get(c1).contains(c2)) {
						graph.get(c1).add(c2);
						inDegrees.put(c2, inDegrees.get(c2) + 1);
					}
					break;
				}
			}
		}
		
		Queue<Character> queue = new LinkedList<>();//找到入度为0的起点
		for(char ch : inDegrees.keySet()) {
			if(inDegrees.get(ch) == 0) {
				queue.offer(ch);
			}
		}
		
		StringBuilder sb = new StringBuilder();//找出其中一条拓扑排序
		while(!queue.isEmpty()) {
			char ch = queue.poll();
			sb.append(ch);
			
			for(char next : graph.get(ch)) {
				inDegrees.put(next, inDegrees.get(next) - 1);
				if(inDegrees.get(next) == 0) {
					queue.offer(next);
				}
			}
		}
		
		return sb.length() == graph.size() ? sb.toString() : "";
	}
	
}
